1. Field of the Invention
The present invention relates to an error correcting decoder using an erasure flag method to correct a bit error arising in transmission or playback of a digital signal.
This application is based on Japanese Patent Application No. 10-374495, the contents of which are incorporated herein by reference.
2. Description of the Related Art
Conventional recording/playback systems for a digital signal of a VTR, an optical disc, or the like, utilize a product code shown in FIG. 11. In this product code, the row direction is defined as C1 (n1, k1), the column direction is defined as C2 (n2, k2), and the rows and the columns are encoded separately. This method is a double decoding in which errors are corrected when decoding the rows, and then the remaining errors are corrected when decoding the columns. Reference characters n1 and n2 indicate code word lengths, and k1 and k2 indicate data code word lengths.
The errors arising when reading the digital signal of the VTR or the optical disc are random errors which occur at random, and burst errors which are continuous due to a damage or dust on a medium. In VTR or optical disc systems, when the burst errors beyond the correction capability arise, the errors are uncorrectable by C1 correction. Subsequently, by the C2 correction, the symbols which were not corrected by the C1 correction are. corrected. Thus, the double encoded product code provides strong and efficient correction. Here, the symbol is a unit of the code word length or of the data code word length.
The C1 correction and the C2 correction will be explained. When the minimum distances between code words are defined as d1 for the C1 correction, and d2 for the C2 correction, the C1 correction can correct at most (d1xe2x88x921)/2 symbols. Further, the C2 correction can correct at most (d2xe2x88x921)/2 symbols. When in C2 correction erasure information is provided by erasure flags, at most (d2xe2x88x921) symbols can be corrected.
The erasure flag indicates the uncorrectable rows in the C1 correction, or the uncorrectable rows and the rows with more than N corrected symbols (N is an integer equal to or above 1) in the C1 correction, as doubtful rows which may include errors. This information is used in the C2 correction.
When d1=11, the C1 correction can correct at most five errors, and the erasure flags are set for the uncorrectable rows which includes six or more errors. Alternatively, because the 5-error correction reaches the limit of the correction capability and the mis-correction rate is high, the erasure flags are set for the uncorrectable rows and the 5-error corrected rows. Thus, by using the erasure flags indicating the location information of the doubtful rows, at most (d2xe2x88x921) symbols can be corrected by the C2 correction.
This conventional technique is described in the xe2x80x9cBackground Artxe2x80x9d of Japanese Patent Application, First Publication No. Hei 7-202719, xe2x80x9cError Correction Code Decoder.xe2x80x9d
While the methods for setting the erasure flags differ depending on systems, the erasure flags are set after the C1 correction period, and are fixed throughout the C2 correction.
In the C2 correction, the following corrections are possible according to the combination of the error symbols without the erasure flags and the number of the erasure flags. When d2=9, 4-error correction only for symbol correction, 8-erasure correction only by the erasure flags, and their combinations, which are 1-error/6-erasure correction, 2-error/4-erasure correction, and 3-error/2-erasure correction, are possible.
Regarding the existence of an error for which the erasure flag is not set in the C2 correction, because the erasure flags are set for the uncorrectable rows, the error-corrected rows include no error if there is no mis-correction. However, mis-corrections stochastically arise, and therefore error correction is necessary even in the C2 correction. The product code by the combination of the C1 correction and the C2 correction can thus provide strong and efficient correction.
The conventional error correcting decoder will be explained with reference to FIG. 5.
The decoder comprises: a C1 correction circuit 1 for performing the C1 correction; an error corrected row counter 2 for counting the numbers of the uncorrectable rows and of the N-error corrected rows in the C1 correction; a row correction state storage circuit 3 for storing the correction states of the rows corrected by the C1 correction; an erasure flag selector 6 for selecting the erasure flags based on the output from the error corrected row counter 2 and row correction state storage circuit 3; and a C2 correction circuit 7 for performing the C2 correction.
As shown in FIG. 7, the error corrected row counter 2 comprises an uncorrectable row detection circuit 10, a (d1xe2x88x921)/2 error corrected row detection circuit 11, a ((d1xe2x88x921)/2xe2x88x921) error corrected row detection circuit 12, . . . , and a 1-error corrected row detection circuit 13, and counters 14 which are in one-to-one correspondence to the detection circuits 10 to 13. The detection circuits 10 to 13 detects the corrected rows, and the counters 14 count total numbers of errors in the C1 correction.
Specifically, when d1xe2x88x9211, the numbers of the uncorrectable rows, 5-error corrected rows, 4-error corrected rows, 3-error corrected rows, 2-error corrected rows, and 1-error corrected rows are counted in the C1 correction period.
FIG. 8 shows the structure of the row correction state storage circuit 3. The row correction state storage circuit 3 comprises: bit conversion circuits 15 in one-to-one correspondence to the detection circuits 10 to 13; and a memory 16 for storing the results of the correction for each row whenever the row is corrected by the C1 correction. The results of the correction are required to determine which error corrected rows the erasure flags for the C2 correction are to be set for. The memory 16 may be, e.g., an FIFO. The memory 16 may store bits indicating the results of the correction.
Specifically, when d1=11, three bits are required. The memory 16 stores, e.g., xe2x80x9c111xe2x80x9d for uncorrectable errors, xe2x80x9c101xe2x80x9d for 5-error correction, xe2x80x9c100xe2x80x9d for 4-error correction, xe2x80x9c011xe2x80x9d for 3-error correction, xe2x80x9c010xe2x80x9d for 2-error correction, xe2x80x9c001xe2x80x9d for 1-error correction, and xe2x80x9c000xe2x80x9d for no error correction.
After the C1 correction, the erasure flag selector 6 selects the erasure flag so as to make the C2 correction for each column efficient.
The algorithm of the erasure flag selector 6 is shown in FIG. 6. Since the error corrected row inevitably includes mis-correction, it is determined in step S11 in FIG. 6 whether the total number of uncorrectable rows, (d1xe2x88x921)/2-error corrected rows, . . . , 1-error corrected rows is equal to or below d2xe2x88x921. These values are stored in the error corrected row counter 2 shown in FIG. 5, and the total number can be calculated from the values.
When the total number is equal to or below d2xe2x88x921, the same number of the erasure flags as the total number is to be set according to xe2x80x9cerasure flags=the total numberxe2x80x9d (step S16). In the C2 correction, based on the state of the error correction for each row stored in the row correction state storage circuit 3, the symbols are read in the column direction, and simultaneously the erasure flags are set for the symbols with which the information indicating one or more error corrected rows is read from the row correction state storage circuit 3, and then the C2 correction is carried out. When in step S11 the total number exceeds d2xe2x88x921, the flow proceeds to the next step S13.
In step S13, it is determined whether the total number of uncorrectable rows, (d1xe2x88x921)/2-error corrected rows, . . . , and 2-error corrected rows is equal to or below d2xe2x88x921. Subsequently, the total number in the selection of the error corrected rows is decremented, to thus obtain the condition when the total number is equal to or below d2xe2x88x921. When the total number of the uncorrectable rows and (d1xe2x88x921)/2-error corrected rows in step S15 is equal to or below d2xe2x88x921, the erasure flags are set for these rows. When the total number is above d2xe2x88x921, the erasure flags are set only for the uncorrectable rows. Then, the C2 correction is carried out.
This example, which is widely used, is simplified, and is effective, is a method for setting the erasure flags only for the uncorrectable rows. The circuit structure, which is shown in FIGS. 5, 7, and 8, may be comprised only of the circuits for handling the uncorrectable rows. The algorithm shown in FIG. 6 includes only step S15, and is therefore considerably simplified. Further, because the bit conversion circuit 15 in FIG. 8 can indicate by only one bit whether the row is correctable or not, the required capacity of the memory 16 may be reduced.
However, because the conventional error correcting decoder performs the C2 correction while fixing the erasure flags after the C1 correction, there is a problem that the erasure flags may not be appropriate for each column.
It is therefore an object of the present invention to provide an error correcting decoder with improved correction capability which can correct a column, which is not corrected by the background art, by selecting a process for setting the erasure flags for each column in the C2 correction.
In order to accomplish the above object, the error correcting decoder using an erasure flag process for a digital signal, according to the present invention, comprises: a row code word corrector for correcting errors in each row; a column code word corrector for correcting errors in each column; a first counter for counting the respective numbers of the uncorrectable rows and of the error corrected rows; a second counter for counting the number of error corrected symbols in each column; a storage device for storing the states of the corrected symbols; and an erasure flag selector for appropriately setting erasure flags for each column, based on the count results and the stored data.
In another aspect of the present invention, when the first total number of uncorrectable rows+(d1xe2x88x921)/2-error corrected rows+ . . . +(N+1)xe2x88x92error corrected rows+N-error corrected rows (d1: the minimum distance between code words in the row correction, N: an integer equal to or below (d1xe2x88x921)/2) is equal to or below d2xe2x88x921 (d2: the minimum distance between code words in the column correction), the erasure flag selector sets the erasure flags for the corresponding symbols. When the total number exceeds d2xe2x88x921 in the previous step and the total number of uncorrectable rows+(d1xe2x88x921)/2-error corrected rows+ . . . +N+1-error corrected rows+N-error corrected symbols is equal to or below d2xe2x88x921, the erasure flag selector sets the erasure flags for the corresponding symbols. Then, N is decremented by one when the total number exceeds d2xe2x88x921 in the previous step, and the first to third steps are repeated. When the total number of uncorrectable rows and (d1xe2x88x921)/2-error correction symbols exceeds d2xe2x88x921, the erasure flag selector sets the erasure flags for the uncorrectable rows.
In another aspect of the invention, the erasure flag selector changes the erasure flags for each column in the column correction.
In another aspect of the invention, the first counter counts the respective numbers of the uncorrectable rows and of the (d1xe2x88x921)/2-error corrected rows, and the second counter for counting the number of (d1xe2x88x921)/2-error corrected symbols (d1: the minimum distance between code words in the row correction).
In another aspect of the invention, when the total number of uncorrectable rows and (d1xe2x88x921)/2-error corrected rows is equal to or below d2xe2x88x921 (d2: the minimum distance between code words in the column correction), the erasure flag selector sets the erasure flags for the corresponding symbols. When in the previous step the total number exceeds d2xe2x88x921 and the total number of uncorrectable rows and the (d1xe2x88x921)/2-error corrected symbols is equal to or below d2xe2x88x921, the erasure flag selector sets the erasure flags for the corresponding symbols. When in the previous step the total number exceeds d2xe2x88x921, the erasure flag selector sets the erasure flags for the uncorrectable rows
According to the present invention, when two or more mis-corrected symbols are not in the same column in the C2 correction, the five symbols out of eleven symbol errors can be corrected. As the number of errors increases, the present invention becomes more effective. For example, although errors in an image signal are inconspicuous because of interpolation, as the number of errors increases, the errors can be visually found. While errors in an audio signal are inconspicuous because of the interpolation, the sound may be unnatural as the number of errors increases. Therefore, the error should not be transmitted to the following system.
The present invention can correct uncorrectable symbols derived from mis-correction, improve the correction capability by the erasure flag control for each column. Further, the invention reduces the transmission of the errors, preventing deterioration of image or audio data.